class Solution {
    public static void main(String[] args) {
        int[] arr = {1,1,1,2,2,2,3,3,3} ;
        System.out.println(findNumberOfLIS(arr));
    }
    public static int findNumberOfLIS(int[] nums) {
       int len = nums.length ;
       int[] dp = new int[len] ;
       int[] g = new int[len] ; 
       for(int i=0 ; i < len ; i ++){
        dp[i] = 1 ;
        g[i] = 1 ;
        for(int j=i-1; j >=0 ; j--){
           if(nums[i] > nums[j]){
               if(dp[j]+1 > dp[i]){
                g[i] = g[j] ;
                dp[i] = dp[j]+1 ;
               } else if(dp[j]+1 == dp[i]){
                g[i] += g[j] ;
             }
           }
        }
       }
       int sum = 0 ; 
       int max = Integer.MIN_VALUE ;
       for(int i=0 ; i < len ;i ++){
         if(dp[i] > max){
            max = dp[i] ;
            sum = g[i] ;
         }else if(dp[i] == max){
            sum += g[i] ;
         }
       }
     return sum ;
    }
}